#include <vector>
class Solution {
public:
    int LIS(vector<int>& arr) {
        int n = arr.size();
        if (n == 0 || n == 1) return n;
        vector<int> dp(n, 1);
        for (int i = 1; i < n; ++i) {
            int maxn = 1;
            for (int j = 0; j < i; ++j) {
                if (arr[j] < arr[i]) {
                    maxn = max(dp[j] + 1, maxn);
                }
            }
            dp[i] = maxn;
        }
        return *max_element(dp.begin(), dp.end());
    }
};